#include <algorithm>
using namespace std;
class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        if (n==0) return 1;
        for (int i=0;i<n;i++) {
            --A[i];
            if (A[i]<0 || A[i]>=n) A[i]=-1;
        }
        for (int i=0;i<n;i++)
            while (A[i]!=-1 && 0<=A[i] && A[i]<n && A[A[i]]!=A[i])
                swap(A[i], A[A[i]]);
        for (int i=0;i<n;i++)
            if (A[i]==-1 || A[i]!=i) return i+1;
        return n+1;
    }
};
